perm filename LISDOC[LSP,WD] blob
sn#010441 filedate 1972-11-01 generic text, type T, neo UTF8
00100 Lisp in Structure and Function
00200
00300 The following is a brief description of the organisation and
00400 functioning of the Stanford Lisp System. It attempts to show Lisp as
00500 it fits into the mold of a PDP-10 program, mentioning those things
00600 shares with all programs and emphasising those features which are
00700 unique to Lisp.
00800 The document is organised into four sections, preceded by a
00900 brief note on the PDP-10. The first deals with program
01000 organisation, the second with data types, the third with the
01100 organisation of the lisp program itself and the fourth with the Lisp
01200 interpreter.
01300
01400 The PDP-10 Computer
01500
01600 The PDP-10 is a fixed word length machine with an address
01700 space of 256K 36 bit words. Each word is therefore capable of
01800 holding two machine addresses. When a word is so regarded, the
01900 addresses will be called pointers. The instruction format is fairly
02000 uniform and is principally that of a single address machine. Each
02100 instruction contains, however, a second address of limited size drawn
02200 from the first fifteen locations. These are referred to as the
02300 "accumulators" though they also serve both as index registers and
02400 ordinary memory locations. In many respects their behavior is that of
02500 the general purpose registers of an IBM 360.
02600
00100 Organisation of the Lisp core image
00200
00300
00400 TOP OF CORE
00500 _____________________________________
00600 | |
00700 | EXPANDED CORE |
00800 |____________________________________|
00900 | |
01000 | SPECIAL PUSHDOWN LIST |
01100 |____________________________________|
01200 | |
01300 | REGULAR PUSHDOWN LIST |
01400 |____________________________________|
01500 | |
01600 | BIT TABLES |
01700 |____________________________________|
01800 | |
01900 | FULL WORD SPACE |
02000 |____________________________________|
02100 | |
02200 | FREE STORAGE |
02300 |____________________________________|
02400 | |
02500 | OBLIST |
02600 |____________________________________|
02700 | |
02800 | BINARY PROGRAM SPACE |
02900 |____________________________________|
03000 | |
03100 | LISP INTERPRETER |
03200 |____________________________________|
03300 | |
03400 | JOB DATA AREA |
03500 |____________________________________|
03600 | |
03700 | ACCUMULATORS |
03800 |____________________________________|
03900 BOTTOM OF CORE
04000
00100 ACCUMULATORS
00200
00300 These are the first sixteen registers of the PDP-10's memory.
00400 They act as second addresses in PDP-10 instructions. Several are
00500 used by Lisp as follows.
00600
00700 0 is reserved for the atom head of the distinguished atom NIL
00800 1 throuh 5 are reserved for arguments of functions
00900 6 is used for the pointer to the arguments of an LSUBR
01000 7 through 13 are used in ad hoc ways by the Lisp system
01100 14 through 17 contain the pointers to Free Storage and full
01200 word space and the stack pointers for the regular and
01300 special push down lists.
01400
01500 JOB DATA AREA
01600
01700 Most of the remaining locations below octal 140 are
01800 consacrated to traps, interupts and communication with the time
01900 sharing system.
02000
02100 LISP INTERPRETER
02200
02300 This is the name normally given to the code of the system
02400 itself. This contains, aside from the interpreter proper, various
02500 things which are usually called runtime routines.
02600
02700 BINARY PROGRAM SPACE
02800
02900 This is the space allocated to code which is added by the
03000 user. It is most commonly inhabited by code generated by the
03100 compiler, though other uses are possible.
03200
03300 OBLIST
03400
03500 The OBLIST is the hash table used by the Lisp read functions
03600 to maintain uniqueness of atoms. It is both a list and an array, in
03700 which the car of each cell points to a list of atoms and the cdr
03800 points to the next cell. These cells must be contiguous in a fixed
03900 location, and are acessed in array fashion by read from the hash
04000 codes of the atoms.
04100
04200 FREE STORAGE
04300
04400 This is a misnomer which has become standard in this system.
04500 It would better be called node space, list sructure space, or
04600 pairword space. Each word in this space is made up of two
04700 pointers(Car and Cdr) which may point to any location in the system.
04800
00100 FULL WORDS
00200
00300 This space contains those words which contain data other than
00400 pointers or instructions. These are of three types: ASCII
00500 characters, fixed point numbers and floating point numbers.
00600
00700 BIT TABLES
00800
00900 This region contains the bit tables used by the garbage
01000 collecter.
01100
01200 REGULAR PUSH DOWN LIST
01300
01400 This to is a misnomer; it is not a list but a stack. It is
01500 used to store the return addresses of function calls, and the local
01600 storage of compiled functions.
01700
01800 SPECIAL PUSH DOWN LIST
01900
02000 This stack has special structure and is used to store the
02100 values of variables which are to be accessed by name. The data it
02200 holds are organised into blocks, where each block contains
02300 information about its own extent and a series of pairwords whose cars
02400 point to atoms and whose cdrs point to former values of these
02500 variables.
02600
02700 EXPANDED CORE
02800
02900 The area from here up to the limits on job size is put to
03000 intermittent use as the resting place for Alvine, the Lisp loader and
03100 anything else(usually code) which the user may see fit to place here.
03200
00100 Data Types
00200
00300
00400 As Lisp is not rich in data types these may be quickly
00500 eneumerated.
00600
00700 SMALL NUMBERS
00800
00900 The Stanford Lisp System is designed to run in no more that
01000 128K. As a result, pointers above that can be recognised as
01100 illegitimate and used for other purposes. Any such pointer is in
01200 fact decoded by adding a suitable offset into a number between
01300 approximatly -64K and +64K.
01400
01500 NUMBERS
01600
01700 All numbers between the above and the limit of machine
01800 precision (approximately 30 billion) are represented as atoms. These
01900 atoms have exactly three words of which the first is a normal atom
02000 header, the second has as its car either the atom FIXNUM or the atom
02100 FLONUM, the third contains the number in suitable format.
02200
02300 IDENTIFIERS
02400
02500 These are the "usual sort" of atoms. The first word of an
02600 atom is referred to as its "atom header". This word contains a -1 in
02700 its left half to distinguish it from ordinary pieces of list
02800 structure. The remainder of an atom is a list, each odd word of
02900 which is the name of a property and each even member of which points
03000 to the value of that property.
03100
03200 LISTS
03300
03400 These are the fundamental structures and consist of sequences
03500 of pairwords each of which points on in two directions to the rest of
03600 the list.
03700
00100 Structure of the "Lisp Interpreter"
00200
00300 The Lisp System code consists of four major portions: the
00400 interpreter itself, a set of supporting routines for doing standard
00500 manipulations of lists, the garbage collector, and the IO.
00600
00700 INTERPRETER
00800
00900 The routines APPLY and EVAL operate on aieces of list
01000 structure to evaluate them according to the rules of the lisp
01100 language. They will be discussed in detail in the last section.
01200
01300 SUPPORTING ROUTINES
01400
01500 These would be called the "run time routines" in compiler
01600 base languages. In the algebraic languages these are typically
01700 numerical routines such as square root. In Lisp the corresponging
01800 functions preform such functions as list searching.
01900
02000 GARBAGE COLLECTOR
02100
02200 This portion of the program is run when either the free
02300 storage or full word spaces are exausted. It begins at places of
02400 known importance such as the OBLIST and the push down list, and marks
02500 all valuable data in the bit tables. When this is complete it passes
02600 through memory consulting these tables and stringing all unused wods
02700 into lists of available words.
02800